package com.kavinz.algo.stack;

import com.kavinz.algo.list.DoublyLinkedList;

/**
 * <Cracking the coding interview><br>
 * Exercise 3.3 Imagine a (literal) stack of plates If the stack gets too high,
 * it might topple There- fore, in real life, we would likely start a new stack
 * when the previous stack exceeds some threshold Implement a data structure
 * SetOfStacks that mimics this SetOf- Stacks should be composed of several
 * stacks, and should create a new stack once the previous one exceeds capacity
 * SetOfStacks push() and SetOfStacks pop() should behave identically to a
 * single stack (that is, pop() should return the same values as it would if
 * there were just a single stack)<br>
 * FOLLOW UP Implement a function popAt(int index) which performs a pop
 * operation on a specific sub-stack
 * 
 * @author Kevin Zhao
 * 
 */
public class SetOfStacks<E> {
	private int STACK_THREHOLD = 5;// uplimit amount of the element an single
									// stack can hold
	DoublyLinkedList<LinkedListStack<E>> stackPool = new DoublyLinkedList<LinkedListStack<E>>();
	LinkedListStack<E> swap = new LinkedListStack<E>();

	public SetOfStacks() {
		LinkedListStack<E> stack = new LinkedListStack<E>();
		stackPool.add(stack);
	}

	public SetOfStacks(int stackThrehold) {
		this();
		this.STACK_THREHOLD = stackThrehold;
	}

	/**
	 * pop elements from the specified stack
	 * 
	 * @param stackNO
	 * @return
	 */
	public E popAt(int stackNO) {
		if (stackNO < 0 || stackNO > stackPool.size() - 1)
			throw new IndexOutOfBoundsException("index out of bounds");
		// pop
		LinkedListStack<E> stack = stackPool.get(stackNO);

		E element = stack.pop();

		// rollover
		rollingOver(stackNO + 1, stack);

		// remove empty stack at the tail of the stack pool
		if(stackPool.get(stackPool.size() - 1).isEmpty())
			stackPool.remove(stackPool.size() - 1);
		return element;

	}

	private void rollingOver(int startStackNO, LinkedListStack<E> stack) {
		if (startStackNO > stackPool.size() - 1)
			return;
		LinkedListStack<E> stackToRollOver = stackPool.get(startStackNO);
		while (stack.size() < STACK_THREHOLD && stackToRollOver.size() != 0) {
			stack.push(stackToRollOver.popBottom());
		}
		//recursive invocation
		rollingOver(startStackNO + 1, stackToRollOver);
	}

	public void push(E element) {
		LinkedListStack<E> lastestStack = stackPool.get(stackPool.size() - 1);
		// stack over capacity
		if (lastestStack.size() >= STACK_THREHOLD) {
			// construct a new stack
			LinkedListStack<E> newStack = new LinkedListStack<E>();
			newStack.push(element);
			// put the newStack into the stackPool
			stackPool.add(newStack);
		} else {
			lastestStack.push(element);
		}
	}

	public E pop() {
		// empty stackPool
		if (stackPool.size() == 0)
			return null;
		LinkedListStack<E> lastestStack = stackPool.get(stackPool.size() - 1);

		E result = lastestStack.pop();
		if (lastestStack.size() == 0)
			stackPool.remove(stackPool.size() - 1);
		return result;
	}

	public int size() {
		int result = 0;
		LinkedListStack<E> lastestStack = stackPool.get(stackPool.size() - 1);
		result += lastestStack.size();

		result += (stackPool.size() - 1) * STACK_THREHOLD;

		return result;
	}

	public int stackAmount() {
		return stackPool.size();
	}

	public static void main(String[] args) {
		SetOfStacks<String> stackSet = new SetOfStacks<String>(2);

		stackSet.push("a");
		stackSet.push("b");
		stackSet.push("c");
		stackSet.push("d");
		stackSet.push("e");
		stackSet.push("f");
		stackSet.push("g");
		stackSet.push("h");
		stackSet.push("j");
		stackSet.push("k");

		// System.out.println("pop:" + stackSet.pop());
		// System.out.println("pop:" + stackSet.pop());
		// System.out.println("pop:" + stackSet.pop());
		// System.out.println("pop:" + stackSet.pop());
		System.out.println("popAt:" + stackSet.popAt(1));
		System.out.println("popAt:" + stackSet.popAt(1));
		System.out.println("size:" + stackSet.size());
		System.out.println("stack amount:" + stackSet.stackAmount());

	}

}
